package Easy.Stack;

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
// 有效字符串需满足：
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 每个右括号都有一个对应的相同类型的左括号。
// 示例 1：
//输入：s = "()"
//输出：true
//
// 示例 2：
//输入：s = "()[]{}"
//输出：true
//
// 示例 3：
//输入：s = "(]"
//输出：false
//
// 提示：
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成

//leetcode submit region begin(Prohibit modification and deletion)
public class ValidParentheses {
    public boolean isValid(String s) {
        // 如果字符串长度为奇数，直接返回false
        if (s.length() % 2 == 1) {
            return false;
        }
        // 使用字符数组模拟栈
        char[] chars = new char[s.length()];
        // 栈顶指针
        int index = 0;
        // 遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            // 判断当前字符，若为左括号则入栈，若为右括号则取栈顶并判断是否匹配
            switch (cur) {
                case '(':
                    chars[index++] = '(';
                    break;
                case '[':
                    chars[index++] = '[';
                    break;
                case '{':
                    chars[index++] = '{';
                    break;
                case ')':
                    if (index == 0 || chars[--index] != '(') {
                        return false;
                    }
                    break;
                case ']':
                    if (index == 0 || chars[--index] != '[') {
                        return false;
                    }
                    break;
                case '}':
                    if (index == 0 || chars[--index] != '{') {
                        return false;
                    }
                    break;
                default:
                    return false;
            }
        }
        return index == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
